Zihan Tan's Homepage
I am a postdoc at DIMACS, Rutgers University. I obtained my PhD from University of Chicago, where I was advised by Prof. Julia Chuzhoy. You can find my CV here (last updated: Apr 2024).
My research interests lie in theoretical computer science, and more specifically graph algorithms. My research focuses on developing modern algorithms for processing massive graphs, especially from the following three aspects:
(i) exploring the limit of graph compression;
(ii) studying graph problems in modern computational models (e.g. sublinear, dynamic, distributed); and
(iii) designing approximation algorithms for fundamental graph problems by exploring the interplay between structural graph theory and graph algorithms.
I co-organized the DIMACS Workshop on Modern Techniques in Graph Algorithms in June 2023 (with Nicole Wein and Prantar Ghosh). Check out the list of videos here.
I am applying for faculty positions in the 2023-2024 cycle.
Email: zihantan1993 at gmail dot com
Publications
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan.
New Structures and Algorithms for Length-Constrained Expander Decompositions
Yu Chen, Zihan Tan.
Lower Bounds on 0-Extension with Steiner Nodes
International Colloquium on Automata, Languages and Programming (ICALP 2024)
Yu Chen, Zihan Tan.
Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
Yu Chen, Zihan Tan.
On (1+ε)-Approximate Flow Sparsifiers
Symposium on Discrete Algorithms (SODA 2024)
Yu Chen, Zihan Tan.
An \sqrt{\log |T|} Lower Bound for Steiner Point Removal
Symposium on Discrete Algorithms (SODA 2024)
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan.
Parallel Greedy Spanners
Yu Chen, Sanjeev Khanna, Zihan Tan.
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
International Colloquium on Automata, Languages and Programming (ICALP 2023)
Zihan Tan, Tianyi Zhang.
Almost Optimal Sublinear Additive Spanners
Symposium on Theory of Computing (STOC 2023) [video by Tianyi]
Zihan Tan, Yifeng Teng, Mingfei Zhao.
Worst-Case Welfare of Item Pricing in the Tollbooth Problem
ACM Web Conference (WWW 2023)
Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, Zihan Tan.
A New Conjecture on Hardness of Low-Degree 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems
Innovations in Theoretical Computer Science (ITCS 2023)
Yu Chen, Sanjeev Khanna, Zihan Tan.
Query Complexity of the Metric Steiner Tree Problem
Symposium on Discrete Algorithms (SODA 2023)
Julia Chuzhoy, Zihan Tan.
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
Symposium on Theory of Computing (STOC 2022)
Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan.
Near Linear ε-Emulators for Planar Graphs
Symposium on Theory of Computing (STOC 2022)
Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, Zihan Tan.
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
Symposium on Discrete Algorithms (SODA 2021)
Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan.
Towards Better Approximation of Graph Crossing Number
Symposium on Foundations of Computer Science (FOCS 2020)
Julia Chuzhoy, Merav Parter, Zihan Tan.
On Packing Low-Diameter Spanning Trees
International Colloquium on Automata, Languages and Programming (ICALP 2020)
Zihan Tan, Liwei Zeng.
On the Inequalities of Projected Volumes and the Constructible Region
SIAM Journal on Discrete Mathematics 33 (2), 694-711, 2019
Julia Chuzhoy, Zihan Tan.
Towards Tight(er) Bounds for the Excluded Grid Theorem
Symposium on Discrete Algorithms (SODA 2019)
Journal of Combinatorial Theory, Series B, 146, 219-265, 2021
Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou.
Robust Influence Maximization
ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2016)
Ioannis Caragiannis, Aris Filos-Ratsikas, Soren Stiil Frederiksen, Kristoffer Arnsfelt Hansen and Zihan Tan.
Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship
The 12th Conference on Web and Internet Economics (WINE 2016)
Mathematical Programming, Series B, 1-30, 2022
Zihan Tan.
On the Computational Complexity of Bridgecard
Journal of Combinatorial Optimization 31 (1), 196-217, 2016
[PDF]
Jiachen Huang, Zihan Tan, Shenghao Yang, Xuan Guang.
Upper Bound on Function Computation in Directed Acyclic Networks
IEEE Information Theory Workshop (ITW 2015)
IEEE Transactions on Information Theory 64 (9), 6454-6459, 2018
Yizhen Zhang, Zihan Tan, Bhaskar Krishnamachari.
On the Meeting Time for Two Random Walks on a Regular Graph, 2014
Talks and Slides
On (1+ε)-Approximate Flow Sparsifiers
Theory Seminar at Boston College, Oct 2023
Theory Seminar at Weizmann Institute of Science, Oct 2023
Almost Optimal Sublinear Additive Spanners
A New Conjecture on Hardness of Low-Degree 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems